#include <cstdio>
#include <iostream>
using namespace std;

void heapAdjust(int num[], int parent, int n)
{
    int temp = num[parent];//保存堆顶元素
    for(int child = 2*parent+1; child <= n; child=2*parent+1)
    {
        if (child+1 <= n && num[child+1] > num[child])//如果右孩子比左孩子小，则定位i到右孩子
            child++;
        if(temp>num[child])//如果最开始的堆顶元素比当前左右孩子中较小的值都小，则以当前节点为根的完全二叉树已经符合大根堆，不用调整
            break;
        num[parent] = num[child];//将左右孩子中较小的值放到父节点
        parent = child;//父节点变成交换的孩子节点
    }
    num[parent] = temp;//将最初的堆顶元素放到最终空的位置
}

void heapSort(int num[], int n)
{
    //建堆
    for (int i = n/2; i >= 0; i--)//从第一个非叶子节点开始，往前逐个进行堆调整，最终建小根堆
        heapAdjust(num,i,n-1);//对顺序存储的完全二叉树进行堆调整

    //输出初次建堆后的情况
    for (int i = 0; i < n; i++)
        cout<<num[i]<<' ';
    cout<<endl;

    //输出并进行堆调整
    for (int i = n-1; i > 0; i--)//从数组最后一个元素开始，一直将最后一个元素跟第一个元素交换，然后调整堆
    {
        //将当前堆中最后一个元素与堆顶元素交换
        int t = num[0];
        num[0] = num[i];
        num[i] = t;

        heapAdjust(num,0,i-1);//从堆顶开始，到i-1，重新调整为大根堆，交换后抛弃原来第一个元素的值

        //输出每次堆调整后的情况
        for (int j = 0; j < n; j++)
            cout<<num[j]<<' ';
        cout<<endl;
    }
}
//On Onlog2n
int main()
{
    int n, num[1000] = {0};
    cin>>n;
    for (int i = 0; i < n; i++)
        cin>>num[i];
    //堆排序
    heapSort(num,n);

    return 0;
}
